package node;

public class MyLinkedList<T> {
    /**
     * 插入数据时，对头节点为空的情况进行了判断，在链表的实现过程中，常用的技巧是插入一个虚拟的头节点，这样就规避掉了每次需要判断链表是否为空的情况。
     * 这个虚拟头结点也是新增、删除、更新链表的发起点。
     */
    private final MyNode<T> dummyHead;
    /**
     * 链表当前元素个数
     */
    private int size;

    public MyLinkedList() {
        // 虚拟头结点
        dummyHead = new MyNode<>(null, null);
        size = 0;
    }

    public MyLinkedList(MyNode<T> realHead) {
        this.dummyHead = new MyNode<>(null, realHead);
        MyNode<T> tmp = realHead;
        size = 0;
        while (tmp != null) {
            tmp = tmp.getNext();
            size++;
        }
    }

    /**
     * 获取链表元素个数
     *
     * @return size num
     */
    public int getSize() {
        return size;
    }

    /**
     * 链表头部插入节点
     *
     * @param value
     */
    public void addFirst(T value) {
        add(0, value);
    }

    /**
     * 链表中部插入节点
     *
     * @param value
     */
    public void add(int index, T value) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index not in rule");
        }
        // 新增时不会使用prev = dummyHead.next，因为当index=0时，虚拟头结点就变成了要插入节点的前一个节点prev，也就是dummyHead是有用的，不能跳过。
        MyNode<T> prev = dummyHead;
        // 查找待插入位置的前一个节点，其索引为index-1
        for (int i = 0; i < index; i++) {
            prev = prev.getNext();
        }
        MyNode<T> newNode = new MyNode<>(value);
        // 需要先把新节点的next指向prev的next，不能先执行prev.setNext(newNode)，否则原来的prev.getNext()就找不到了
        newNode.setNext(prev.getNext());
        // prev的next指向新节点
        prev.setNext(newNode);
        // 链表大小+1
        size++;
    }

    /**
     * 链表尾部插入节点
     *
     * @param value
     */
    public void addLast(T value) {
        add(size, value);
    }

    /**
     * 获取链表中指定位置的节点值
     *
     * @param index
     * @return
     */
    public T get(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index not in rule");
        }
        // dummyHead是个虚拟头节点，其value始终为null，不参与遍历。
        // dummyHead.next等于索引为0处的第一个值。
        MyNode<T> current = dummyHead.getNext();
        // 遍历链表
        for (int i = 0; i < index; i++) {
            current = current.getNext();
        }
        return current.getValue();
    }

    /**
     * 获取链表头值
     *
     * @return
     */
    public T getFirst() {
        return get(0);
    }

    /**
     * 获取链表尾值
     *
     * @return 删除节点的数据
     */
    public T getLast() {
        return get(size - 1);
    }

    /**
     * 删除指定位置的节点
     *
     * @param index 索引
     * @return 删除节点的数据
     */
    public T removeByIndex(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index not in rule");
        }

        // 按索引删除时不会使用prev = dummyHead.next，因为当index=0时，虚拟头结点就变成了要删除节点的前一个节点prev，也就是dummyHead是有用的，不能跳过。
        MyNode<T> prev = dummyHead;
        // 查找待删除位置的前一个节点，其索引为index-1
        for (int i = 0; i < index; i++) {
            prev = prev.getNext();
        }

        // 要删除的节点下表为index，即为索引为index-1的节点的next
        MyNode<T> removedNode = prev.getNext();
        // 把索引为index-1的节点的next设置为要删除的节点的next，这样就断开了原有的index-1到index的链接，重新建立了index-1到index+1的链接（当然，原来的index+1此时变为index）
        prev.setNext(removedNode.getNext());
        // 把要删除的节点的next置为null，便于垃圾回收
        removedNode.setNext(null);
        // 链表大小-1
        size--;

        return removedNode.getValue();
    }

    /**
     * @param value 删除所有值为value的节点
     */
    public void removeAll(T value) {
        // 删除所有值为value的节点时不会使用prev = dummyHead.next，因为当删除节点的index=0时，虚拟头结点就变成了要删除节点的前一个节点prev，也就是dummyHead是有用的，不能跳过。
        MyNode<T> current = dummyHead;

        while (current.getNext() != null) {
            // current.next.value等于value时，说明current.next是要删除的元素
            if (current.getNext().getValue().equals(value)) {
                // 先获得removedNode
                MyNode<T> removedNode = current.getNext();
                // 假设current的下标为index，则是和index+2的节点建立链接
                current.setNext(removedNode.getNext());
                // 经过上一步，此时current已经和removedNode解除引用关系，也就是removedNode不再是current.next，所以可以将removedNode的next置为null，以便垃圾回收。
                removedNode.setNext(null);
//                break; // 如果只想删除第一个值为value的，这里就可以退出循环了
            } else {
                // 否则遍历
                current = current.getNext();
            }
        }
    }

    /**
     * 删除第一个节点
     *
     * @return 删除节点的数据
     */
    public T removeFirst() {
        return removeByIndex(0);
    }

    /**
     * 删除最后一个节点的数据
     *
     * @return 删除节点的数据
     */
    public T removeLast() {
        return removeByIndex(size - 1);
    }

    /**
     * 设置指定位置的节点的值
     *
     * @param index 索引
     * @param value 值
     */
    public void set(int index, T value) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index not in rule");
        }
        // dummyHead.next 等于索引为0处的第一个值
        // set不会修改dummyHead的值，所以current从dummyHead.next开始
        MyNode<T> current = dummyHead.getNext();
        for (int i = 0; i < index; i++) {
            current = current.getNext();
        }
        current.setValue(value);
    }

    /**
     * 判断是否包含某个值
     *
     * @param value 值
     * @return true 包含，false 不包含
     */
    public boolean contains(T value) {
        MyNode<T> current = dummyHead.getNext();
        while (current != null) {
            if (current.getValue().equals(value)) {
                return true;
            }
            current = current.getNext();
        }
        return false;
    }

    /**
     * 反转链表，参考：https://www.cnblogs.com/keeya/p/9218352.html
     */
    public MyLinkedList<T> reverse() {
        MyNode<T> first = dummyHead.getNext();
        MyNode<T> reversedNode = reverseByTraverse(first);
        return new MyLinkedList<>(reversedNode);
    }

    private MyNode<T> reverseByRecursion(MyNode<T> current) {
        if (current == null || current.getNext() == null) {
            return current;
        }
        MyNode<T> oldNext = current.getNext();
        MyNode<T> newHead = reverseByRecursion(oldNext);
        oldNext.setNext(current);
        current.setNext(null);
        return newHead;
    }

    private MyNode<T> reverseByTraverse(MyNode<T> current) {
        MyNode<T> pre = null;
        while (current != null) {
            // 记住当前节点的下个节点，便于后面current的向后移动
            MyNode<T> oldNext = current.getNext();
            // 断开原来的current和oldNext的链接，反转为current和pre的链接
            current.setNext(pre);
            // 下面这两步是在遍历，pre和current都在链表中向后移动
            pre = current;
            current = oldNext;
        }
        return pre;
    }

    public void print() {
        MyNode<T> current = dummyHead.getNext();
        while (current != null) {
            System.out.println(current.getValue());
            current = current.getNext();
        }
    }
}
